function fib (n:number):number {
    // 1.定义状态
    // dp保留菲波那切数列中每一个位置对应的值(状态)
    // dp[x]就是x位置对应的状态
    // 2.状态转移方式 dp[i] = dp[i - 1] + dp [i -2]
    // 状态转移方程一般情况下是写在循环里面的(for/while)中
    // 3.设置初始化状态: dp[0]/dp[1] 初始化状态
    // 4.计算最终结果
    
    // 1.定义状态
    const dp:number[] = [];
    // 2.初始化状态
    dp[0] = 0;
    dp[1] = 1
   
    for (let i = 2; i <= n; i++) {
        // 3.状态转移方程
        dp[i] = dp[i - 1] + dp[i -2];
    }
    // 4.计算最终结果
    return dp[n];
}


console.log(fib(10))
console.log(fib(50))

export {}